/**
 * 给定二维数组，对每个3*3的区域检查是否符合条件
 * 如果是，则计算平均值，并加到这9个元素的位置
 * 最后再对每一格算一个平均值即可
 * O(9NM)
 */
class Solution {
public:
    vector<vector<int>> resultGrid(vector<vector<int>>& image, int threshold) {
        int n = image.size();
        int m = image[0].size();

        vector<vector<int>> ans(n, vector<int>(m, 0));
        vector<vector<int>> cnt(n, vector<int>(m, 0));

        for(int i=0;i+3<=n;++i)for(int j=0;j+3<=m;++j){
            if(not isOK(image, i, j, threshold)) continue;
            proc(image, i, j, ans, cnt);
        }
        for(int i=0;i<n;++i)for(int j=0;j<m;++j) {
            if(cnt[i][j]){
                ans[i][j] /= cnt[i][j];
            }else{
                ans[i][j] = image[i][j];
            }
            
        }
        return ans;
    }


    bool isOK(const vector<vector<int>>& image, int r, int c, int thresh){
        for(int i=r;i<r+3;++i)for(int j=c;j<c+3;++j){
            if(j + 1 < c + 3){
                auto cha = image[i][j] - image[i][j + 1];
                if(cha < 0) cha = -cha;
                if(cha > thresh) return false;                
            }

            if(i + 1 < r + 3){
                auto cha = image[i][j] - image[i + 1][j];
                if(cha < 0) cha = -cha;
                if(cha > thresh) return false;                
            }

        }
        return true;
    }

    void proc(const vector<vector<int>>& image, int r, int c, vector<vector<int>>& ans, vector<vector<int>>& cnt){
        int tmp = 0;
        for(int i=r;i<r+3;++i)for(int j=c;j<c+3;++j){
            tmp += image[i][j];
        }
        tmp /= 9;
        for(int i=r;i<r+3;++i)for(int j=c;j<c+3;++j){
            ans[i][j] += tmp;
            cnt[i][j] += 1;
        }
        return;
    }
};